/*
3249.统计好节点的数目 
https://leetcode.cn/problems/count-the-number-of-good-nodes/description/
中等 2024/11/10
*/

class Solution {
public:
    int ans=0;
    vector<vector<int>>mp;
    int dfs(int i,int fu){
    int n=1,k=0; //用来记录子树的大小，用于跟递归另一边后的结果比较
    bool flag=true;
    for(int j : mp[i]){
        if(j==fu) continue;  //不要递归到父节点
        int t=dfs(j,i);
        if(k==0)
        k=t; //记录第一个儿子子树的大小
        else if(k!=t)//判断子树之间是否相同
        flag=false;
        n+=t;//记录一边的子树多长   
    }
    if(flag)
    ans++;
    return n;
}
    int countGoodNodes(vector<vector<int>>& edges) {
        int n=edges.size()+1;
        mp.resize(n);
        for(auto it:edges)
        {
            mp[it[0]].push_back(it[1]);//无向树，不知道父节点和子节点是谁
            mp[it[1]].push_back(it[0]);
        }
        dfs(0,-1); //传入根节点跟他的父节点(无,所以传-1)
        return ans;
    }
};